package Demo56;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 合并k个升序链表
 * https://leetcode.cn/problems/merge-k-sorted-lists/
 */
class Solution {
    /**
     * 使用 分治 -> 递归的 方式
     */
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        ListNode ret = marget(lists,0,len -1);
        return  ret;
    }

    private ListNode marget(ListNode[] lists, int begin, int end) {
        if(begin > end) {
            return null;
        }
        if(begin == end) {
            return lists[begin];
        }
        int mid = (begin + end ) / 2;
        ListNode r1 = marget(lists,begin,mid);
        ListNode r2 = marget(lists,mid + 1,end);

        ListNode ret = new ListNode(0);
        ListNode prve = ret;

        while(r1 != null && r2 != null) {
            if(r1.val < r2.val) {
                prve.next = r1;
                prve = r1;
                r1 = r1.next;
            }else {
                prve.next = r2;
                prve = r2;
                r2 = r2.next;
            }
        }
        if(r1 != null) {
            prve.next = r1;
        }
        if(r2 != null) {
            prve.next = r2;
        }
        return ret.next;
    }

    /**
     *  使用优先级队列实现
     */
    public ListNode mergeKLists1(ListNode[] lists) {
        int len = lists.length;
        ListNode ret = new ListNode();
        PriorityQueue<ListNode> queue = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
        for(ListNode head : lists) {
            if(head != null) {
                queue.offer(head);
            }
        }

        ListNode newHead = ret;

        while (!queue.isEmpty()) {
            ListNode cur = queue.poll();
            newHead.next = cur;
            newHead = cur;
            cur = cur.next;
            if(cur != null) {
                queue.add(cur);
            }
        }
        return ret.next;
    }
}